      1  import java.util.NoSuchElementException;

      2

      3  /**

      4     An implementation of a queue as a circular array.

      5  */

      6  public class CircularArrayQueue

      7  {

      8     private Object[] elements;

      9     private int currentSize;

     10     private int head;

     11     private int tail;

     12

     13     /**

     14        Constructs an empty queue.

     15     */

     16     public CircularArrayQueue()

     17     {

     18        final int INITIAL_SIZE = 10;

     19        elements = new Object[INITIAL_SIZE];

     20        currentSize = 0;

     21        head = 0;

     22        tail = 0;

     23     }

     24

     25     /**

     26        Checks whether this queue is empty.

     27        @return true if this queue is empty

     28     */

     29     public boolean empty() { return currentSize == 0; }

     30

     31     /**

     32        Adds an element to the tail of this queue.

     33        @param newElement the element to add

     34     */

     35     public void add(Object newElement)

     36     {

     37        growIfNecessary();

     38        currentSize++;

     39        elements[tail] = newElement;

     40        tail = (tail + 1) % elements.length;

     41     }

     42

     43     /**

     44        Removes an element from the head of this queue.

     45        @return the removed element

     46     */

     47     public Object remove()

     48     {

     49        if (currentSize == 0) { throw new NoSuchElementException(); }

     50        Object removed = elements[head];

     51        head = (head + 1) % elements.length;

     52        currentSize--;

     53        return removed;

     54     }

     55

     56     /**

     57        Grows the element array if the current size equals the capacity.

     58     */

     59     private void growIfNecessary()

     60     {

     61        if (currentSize == elements.length)

     62        {

     63           Object[] newElements = new Object[2 * elements.length];

     64           for (int i = 0; i < elements.length; i++)

     65           {

     66              newElements[i] = elements[(head + i) % elements.length];

     67           }

     68           elements = newElements;

     69           head = 0;

     70           tail = currentSize;

     71        }

     72     }

     73  }